import java.util.HashMap;

// 实现一个自定义的模拟hashMap
class MyHashMap{
    static class Node{
        public int key;
        public String val;
        Node next;
        public Node(int key, String val){
            this.key = key;
            this.val = val;
        }
    }

    Node[] array = new Node[8];
    int usedSize = 0;

    // 计算并返回负载因子
    private float loadFactor(){
        return usedSize*1.0f/array.length;
    }
    // 负载因子>=0.75时，扩容数组长度，并将链表中的节点重新哈希
    private void resize(){
        Node[] newArray = new Node[2*array.length];
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            while (cur != null){
                int indexResize = cur.key % newArray.length;  // 计算array里的每个节点重新哈希的地址

                Node curNext = cur.next;
                cur.next = newArray[indexResize];
                newArray[indexResize] = cur;
                cur = curNext;
            }
        }
        array = newArray;
    }


    // 新增
    public void put(int key, String val){
        // 1.通过key和hash函数计算新增节点在数组上的下标下的链表，查找是否有相同的key，有则替换
        int indexAdd = key % array.length;
        Node cur = array[indexAdd];
        while (cur != null){
            if(cur.key == key){
                cur.val = val;
                return;
            }
            cur = cur.next;
        }
        // 2.没有相同的key，则使用头插法插入新节点
        Node newNode = new Node(key, val);
        newNode.next = array[indexAdd];  // 注意：array[indexAdd]就是数组下标为indexAdd的链表的第一个节点。
        array[indexAdd] = newNode;
        ++usedSize;

        // 3.超过负载因子，就增长数组长度，并重新哈希。
        if(loadFactor() >= 0.75){
            resize();
        }

    }

    // 获取key的val
    public String get(int key){
        int indexGet = key % array.length;
        Node cur = array[indexGet];
        while (cur != null){
            if(cur.key == key){
                return cur.val;
            }
            cur = cur.next;
        }
        return null;
    }
}
public class Main {
    public static void main(String[] args) {
        MyHashMap map = new MyHashMap();
        map.put(1,"yi");
        map.put(8,"ba");
        map.put(3,"san");
        map.put(9,"jiu");
        map.put(4,"si");
        map.put(13,"shisan");
        map.put(17,"shiqi");
        System.out.println(map.get(13));

    }
}
